A computer system may copy data from a storage device into a cache memory. Memory access times may be reduced when storage requests by the computer system are serviced from the faster cache memory. When the cache fills up, the computer system may invalidate data in some cache lines and repopulate the cache lines with other data from the slower storage device.
Different criteria may be used for replacing data in the cache lines. For example, the cache may use a least recently used (LRU) scheme that replaces data in the least recently accessed cache lines with data recently accessed data from the storage device. In another example, the cache may use a least frequently used (LFU) scheme that replaces data in the cache lines with the fewest number of accesses with the data recently accessed from the storage device. Some memory systems may use a combination of the LRU scheme and the LFU scheme. Derivative systems (such as ARC) have been used to improve the effectiveness of caching in storage systems.
The LRU scheme and/or the LFU scheme still may not provide the most efficient and/or effective replacement of data in the cache. For example, a first set of data may be invalidated in the cache while a second set of data in the cache remains valid. The computer system may then request the first set of data while the second set of data remains unused in the cache. The computer system may experience slower memory access times since the first set of data now has to be accessed from the slower storage device. Additionally, the presence of multiple layers of cache at different levels of hierarchy can cause inefficiencies and unforeseen interactions.